
	
	1. Reteaua de scoli

Un numar oarecare de scoli sunt conectate in retea, intre ele stabilindu-se
anumite intelegeri. Fiecare scoala poseda o lista de scoli carora le
distribuie software ("scoli receptoare"). Daca B apare in lista scolii A, nu
este obligatoriu ca si A sa apara in lista scolii B.
Scrieti un program care calculeaza numarul minim de scoli care trebuie sa
primeasca cate o copie a unui nou software, pentru ca acesta sa ajunga la
toate scolile din retea, folosind intelegerile (subproblema A). Pentru
obiectivul urmator, trebuie sa ne asiguram ca trimitand copia unui nou
software catre o scoala aleasa arbitrar, acest software va ajunge la toate
scolile din retea. Pentru a realiza aceasta putem extinde listele
"scolilor receptoare" cu noi membri. Calculati numarul minim de extensii
care trebuiesc realizate astfel incat oricare ar fi scoala catre care
trimitem noul software, acesta va ajunge la toate celelalte scoli
(subproblema B). O extensie inseamna introducerea unui nou membru in lista
receptorilor unei scoli.

Intrare

 Prima linie a fisierului INPUT.TXT contine un intreg N: numarul scolilor
 din retea (2=F3N=F3100). Scolile sunt identificate de primele N numere int=
regi
 pozitive. Fiecare din urmatoarele N linii contine o lista de "scoli
 receptoare". Linia i+1 contine identificatorii "scolilor receptoare"
 corespunzatoare scolii i. Fiecare lista se termina cu un 0. O lista vida
 contine numai un 0 pe linie.

Iesire

 Programul va scrie doua linii in fisierul OUTPUT.TXT. Prima linie va
 contine solutia subproblemei A (un numar intreg pozitiv). A doua linie
 contine solutia subproblemei B.

Exemplu

Pentru fisierul INPUT.TXT:
5
2 4 3 0
4 5 0
0
0
1 0

fisierul OUTPUT.TXT va fi:
1
2
---------------------------------------
		2. Joc

Sa consideram urmatorul joc intre doi jucatori. Se pleaca de la o secventa
de numere intregi pozitive. Cei doi jucatori actioneaza alternativ. Cand ii
vine randul, un jucator alege un numar situat la marginea secventei
(stanga sau dreapta). Numarul selectat este sters din secventa. Jocul se
termina cand toate numerele au fost sterse. Primul jucator castiga daca suma
numerelor pe care le-a selectat este mai mare sau egala decat suma
numerelor selectate de al doilea jucator. Al doilea jucator joaca cat mai
bine posibil.

Primul jucator incepe jocul.

Se cunoaste ca, daca initial secventa contine un numar par de elemente,
atunci primul jucator are o strategie de castig.
Scrieti un program care implementeaza strategia de castig a primului jucator.
Raspunsul celui de al doilea jucator este asigurat de un program dat. Cei doi
jucatori comunica prin trei proceduri ale modulului Play, accesibil
programului. Aceste proceduri sunt StartGame, MyMove si YourMove. Primul
jucator incepe jocul executand procedura fara parametri StartGame. Daca primul
jucator selecteaza un numar din capatul stang al secventei, el executa
procedura MyMove('L'). Similar, prin executarea instructiunii MyMove('R'), el
trimite un mesaj catre al doilea jucator indicandu-i ca a selectat un numar
din capatul drept al secventei. Al doilea jucator (calculatorul) muta imediat
si primul jucator poate afla aceasta mutare executand instructiunea
YourMove(C) unde C este o variabila tip caracter. Valoarea lui C este 'L' sau
'R' dupa cum selectia elementului s-a facut din marginea stanga, respectiv
dreapta a secventei.

Intrare

Prima linie a fisierului INPUT.TXT contine numarul N de elemente din secventa.
N este par si 2=F3N=F3100. Celelalte N linii contin fiecare cate un numar,
reprezentand secventa de la stanga la dreapta.
Fiecare numar are valoarea maxim 200.

Iesire

 Cand jocul s-a sfarsit, programul va scrie rezultatul final al jocului in
 fisierul OUTPUT.TXT. Fisierul contine doua numere pe prima linie. Primul
 numar este suma elementelor selectate de primul jucator iar al doilea numar
 este suma elementelor selectate de al doilea jucator. Programul vostru
 trebuie sa joace un joc si iesirea trebuie sa corespunda acestuia.

Exemplu

Pentru fisierul INPUT.TXT:
6
4
7
2
9
5
2

un fisier OUTPUT.TXT posibil poate fi:
15 14

=======================================
		3. Prelucrarea pieselor

Se considera o linie de productie intr-o fabrica. Asupra unei piese trebuiesc
efectuate doua operatii: intai operatia "A", apoi operatia "B". Fiecare din
aceste operatii este efectuata de un anumit numar de masini. Figura 1 arata
organizarea liniei de productie, care lucreaza astfel: o masina de tip "A" ia
o piesa din magazia de intrare, realizeaza operatia "A" si pune piesa in
magazia intermediara. O masina de tip "B" ia o piesa din magazia intermediara,
realizeaza operatia "B" si pune piesa in magazia de iesire. Toate masinile
pot lucra in paralel si independent una de alta. Capacitatea fiecarei magazii
este nelimitata. Masinile au caracteristici diferite de performanta, fiecare
masina putand executa operatia respectiva intr-un timp propriu.
Scrieti un program care calculeaza timpul minim necesar pentru a realiza
operatia A asupra a N piese (subproblema A). Se considera ca activitatea
incepe la momentul 0.
Calculati de asemenea timpul minim necesar pentru a realiza ambele operatii
asupra celor N piese (subproblema B).

Intrare

Fisierul INPUT.TXT contine numere intregi pozitive pe cinci linii. Prima
linie contine N, numarul de piese (1<N<1000). Pe linia a doua este numarul
M1 masini de tip "A" (1<M1<30). Pe linia a treia sunt M1 numere intregi
reprezentand timpii de prelucrare proprii pentru fiecare masina de tip "A".
Liniile patru si cinci contin numarul M2 de masini de tip "B" (1<M2<30),
respectiv timpii de prelucrare pentru fiecare masina de tip "B". Timpul de
prelucrare al unei piese este masurat in unitati de timp si este format din
timpul necesar luarii unei piese dintr-o magazie, prelucrarea ei si depunerea
in alta magazie. Fiecare timp de prelucrare este cel putin 1 si cel mult 20

Iesire

Programul va scrie doua linii in fisierul OUTPUT.TXT. Prima linie contine un
numar intreg pozitiv: solutia subproblemei A. A doua linie contine solutia
subproblemei B.

Exemplu

Pentru fisierul INPUT.TXT:
5
2
1 1
3
3 1 4

fisierul OUTPUT.TXT va fi:
3
5
=========================================

		4. Ordonarea unei secvente trivalente

Ordonarea este una din problemele cele mai frecvent intalnite. Vom considera
un caz special de ordonare, cand inregistrarile care se sorteaza au cel mult
trei valori distincte. Aceasta se intampla de exemplu cand ordonam premiantii
unei competitii dupa valorile medaliilor, adica medaliati cu aur (primii),
argint (locul 2) si bronz (locul 3). In aceasta problema valorile posibile
sunt numerele intregi 1, 2 si 3. Se cere sortarea lor in ordine
nedescrescatoare. Sortarea va fi realizata printr-o secventa de operatii de
interschimbare. Operatia de interschimbare este definita de doua pozitii
p si q si realizeaza interschimbarea elementelor situate pe aceste pozitii.
Se da o secventa de valori. Scrieti un program care calculeaza numarul minim
de operatii de interschimbare necesare obtinerii secventei sortate
(subproblema A). in plus, construiti o secventa de operatii de
interschimbare care realizeaza aceasta ordonare (subproblema B).

Intrare

Prima linie a fisierului INPUT.TXT contine numarul N de valori (1<N<1000).
Fiecare din urmatoarele N linii contine cate o valoare.

Iesire

Scrieti pe prima linie a fisierului OUTPUT.TXT numarul minim L de operatii
de interschimbare necesare ordonarii secventei (subproblema A). Urmatoarele
L linii dau secventa de operatii de inteschimbare, in ordinea aplicarii lor.
Fiecare linie contine o operatie de interschimbare descrisa prin doua numere
p si q, pozitiile celor doua elemente care se interschimba (subproblema B).
Pozitiile sunt numerotate cu numere de la 1 la N.

Exemplu:

Pentru fisierul INPUT.TXT:
9
2
2
1
3
3
3
2
3
1

fisierul de iesire OUTPUT.TXT poate fi:
4
1 3
4 7
9 2
5 9
---------------------------------------

		5. Cel mai lung prefix

Anumite structuri biologice pot fi reprezentate prin secvente de constituenti.
Acesti constituenti sunt notati cu litere mari. Biologii sunt interesati in
descompunerea unei secvente lungi in altele mai scurte. Aceste secvente
scurte sunt numite primitive. Spunem ca o secventa S poate fi compusa dintr-o
multime data P de primitive, daca exista n primitive p1,p2,...,pn in P astfel
incat S sa se obtina prin concatenarea lor. Prin concatenarea primitivelor
p1,p2,...,pn  intelegem scrierea lor in aceasta ordine, fara spatii. Aceeasi
primitiva poate apare in concatenare de mai multe ori sau poate lipsi. De
exemplu, secventa ABABACABAAB poate fi obtinuta din multimea de primitive
=09=09{A, AB, BA, CA, BBC}
Primele K caractere ale lui S formeaza prefixul lui S de lungime K. Scrieti
un program care accepta la intrare un set P de primitive si o secventa T
formata din constituenti. Programul trebuie sa calculeze lungimea celui
mai lung prefix al secventei T care poate fi obtinut cu primitive din P.

Intrare

 Datele de intrare apar in doua fisiere. Fisierul INPUT.TXT descrie multimea
 P de primitive, iar fisierul DATA.TXT contine secventa T de examinat. Prima
 linie din INPUT.TXT contine N, numarul de primitive din P (1=F3N=F3100). Fiecare
 primitiva este scrisa pe cate doua linii consecutive: prima linie contine
 lungimea L a primitivei (1=F3L=F320); pe a doua linie se afla un sir de L
 litere mari (de la 'A' la 'Z'). Cele N primitive sunt distincte.
 Fiecare linie din fisierul DATA.TXT contine o litera mare pe prima pozitie.
 Fisierul se termina cu o linie formata dintr-un singur caracter punct ('.').
 Lungimea secventei este intre 1 si 500 000.

Iesire

Scrieti pe prima linie a fisierului OUTPUT.TXT lungimea celui mai lung
prefix al lui T care poate fi format din elemente ale multimii P.

Exemplu:

Pentru intrarea:
INPUT.TXT		DATA.TXT
5			A
1			B
A			A
2			B
AB			A
3			C
BBC			A
2			B
CA			A
2			A
BA			B
			C
			B
			.


fisierul de iesire OUTPUT.TXT va fi
11
-------------------------------------------

		6. Patrate magice

	1 2 3 4
	8 7 6 5
Figura 1 : configuratie initiala

Datorita succesului cubului magic, Rubik a inventat versiunea in plan,
numita patrate magice. Este o configuratie sub forma de dreptunghi format
din opt patrate de marimi egale (vezi figura 1). Patratele sunt conectate
astfel incat pozitiile lor pot fi modificate prin diverse miscari.
In problema consideram situatia in care cele opt patrate au culori diferite.
Culorile sunt numerotate cu primele opt numere intregi pozitive. O
configuratie este data de secventa de culori obtinuta citind culorile
patratelor incepand cu coltul stanga sus si mergand in sensul acelor de
ceasornic. De exemplu configuratia din figura 1 este data de secventa
(1,2,3,4,5,6,7,8). Aceasta configuratie este configuratia initiala.
Unei configuratii ii pot fi aplicate trei transformari de baza, notate cu
literele 'A','B','C':
'A': permutarea primei linii cu a doua;
'B': deplasarea circulara a dreptunghiului spre dreapta cu o pozitie ;
'C': rotirea, cu o pozitie, in sensul acelor de ceasornic a celor patru
=09 patrate din mijloc.
Efectele acestor transformari sunt prezentate in figura 2.

A 8 7 6 5		B 4 1 2 3		C 1 7 2 4
  1 2 3 4            	  5 8 7 6		  8 6 3 5

		Figura 2: transformarile de baza

Numerele din afara patratelor semnifica pozitiile patratelor. Daca un patrat
din pozitia p contine numarul i, dupa aplicarea transformarii, patratul a
carui pozitie a fost i inaintea transformarii se misca pe pozitia p.
Scrieti un program care calculeaza o secventa de transformari de baza, prin
care configuratia din figura 1 se transforma intr-o configuratie specificata
la intrare (subproblema A).
Doua puncte se acorda in plus pentru solutie, daca lungimea secventei de
transformari nu depaseste 300 (subproblema B).

Intrare

Fisierul INPUT.TXT contine pe prima linie opt numere intregi pozitive:
descrierea configuratiei finale.

Iesire

Pe prima linie a fisierului OUTPUT.TXT, programul va scrie lungimea L a
secventei de transformari. Pe urmatoarele L linii trebuie scrisa secventa
identificatorilor transformarilor folosite, cate o litera pe prima pozitie
a fiecarei linii.

Remarca
MTOOL.EXE este un program in directorul problemei care va permite sa va
jucati cu patratele magice. Executand "mtool input.txt output.txt" puteti
experimenta diverse exemple.

Exemplu

Pentru fisierul de intrare INPUT.TXT:
2 6 8 4 5 7 3 1

Fisierul de iesire OUTPUT.TXT poate fi:
 7
B
C
A
B
C
C
B
